#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
插入排序
① 从第一个元素开始，该元素可以认为已经被排序
② 取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④ 重复步骤③，直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置后
⑥ 重复步骤②~⑤
"""


def insertion_sort(arr: list) -> list:
    for i in range(len(arr)):
        temp = arr[i]
        for j in range(i, -1, -1):
            if temp < arr[j]:
                arr[j + 1] = arr[j]
                arr[j] = temp

    return arr


if __name__ == '__main__':
    arr = [2, 5, 6, 3, 1, 7, 9, 8]
    new_arr = insertion_sort(arr)
    print(new_arr)
